It should be appreciated that the artificial intelligence branch of computer science has exhibited explosive growth in recent years. One facet of AI has been concerned with the modeling and use of inference systems. Such inference systems exploit the computer science formalism termed "rewrite" or "production" systems. At a minimum, a rewrite or production system includes an alphabet, an initial set of strings (axioms) defined over the alphabet, and a set of production or rewrite rules from which new strings (theorems) can be obtained.
Peter Jackson, "Introduction to Expert Systems", Addison-Wesley Publishing Co., copyright 1986, pp. 29-51 and 126-141, points out that an AI production system comprises a rule set (sometimes called production memory), a rule interpreter that decides how and when to apply the rules, and a working memory that holds data, goals, and intermediate results.
Brownston et al, "Programming Expert Systems in OPS5", Addison-Wesley Publishing Co., copyright 1985, pp. 4-31, contrast a rule-based production computational model with that of a procedural model. More particularly,
Brownston describes a production system as an executable set of production rules in which each rule in such a system represents an ordered pair of a condition (state set) and action statements. This leads to Brownston's characterization of a production system as an unordered finite sequence of data-sensitive production rules.
______________________________________ Brownston's Comparison Production System Model Procedural Model of Computation of Computation ______________________________________ Program Description: Program Description: A description of data An ordered list of expressed as objects, instructions written in attributes, and values, a language with a well- and an unordered finite defined syntax and sequence of rules that semantics. The list has can be referenced by the a specified beginning. data. Each rule consists The language includes a of a condition/pattern stop/halt instruction or part and an action part. punctuation whose meaning is to cease instruction execution. Execution: Execution: Requires maintenance of a The instructions are global data base containing directly executable. the problem description and The first instruction any modifications, in the list initiates additions, or deletions execution. After this, thereto and a recognize, execution proceeds in resolve, act (RRA) or match, sequence punctuated by select, execute cycle. The conditional branches cycle: until a stop or halt instruction is encountered. (a) identifies that subset of rules having a condition or pattern part matching the data, (b) selects at least one rule from the identified subset of rules according to an extrinsic protocol, and (c) executes (fires) the action prescribed by the action part of the selected rule including modification to the data base. ______________________________________
In addition to Jackson and Brownston, reference should also be made to:
(1) Miranker, "TREAT: A Better Match Algorithm for AI Production Systems", Proceedings of the AAAI-87 Sixth National Conference on Artificial Intelligence, Vol. 1, July 13-17, 1987, pp. 42-47. PA0 (2) Miranker, Dept. of Computer Science, University of Texas at Austin, Report TR-87-03, January 1987. PA0 (3) Forgey, "OPS5 Users Manual", CMU-CS-81-135, copyright 1981. PA0 (4) Forgey, "Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem", Artificial Intelligence, Vol. 19, copyright 1982, pp. 17-37. PA0 (5) Schor et al, "Advances in Rete Pattern Matching", Proceedings of AAAI '86. PA0 (6) Chambers et al, "Distributed Computing", Academic Press, copyright 1984, pp. 10-19. PA0 (7) Aho et al, "Compilers: Principles, Techniques, and Tools", Addison-Wesley Publishing Co., copyright 1986, pp. 608-632.
Brownston, Miranker, Forgey, and Schor describe pattern-driven, forward-chaining production systems using a matching-rule, select-rule, execute-rule cycle based on the OPS5 AI language. Furthermore, these references point out that the process of many data-object/many pattern matching is the most computationally intensive phase in the production system control cycle.
The references teach several techniques for reducing the computational intensity of the pattern-matching phase. First, advantage can be taken of the temporal redundancy of the data objects resident in working memory. That is, the set of objects over which the pattern portions of the rules are compared can be limited to those objects in working memory which have been either created or modified since the last cycle. Second, the many object/many pattern comparison can be systematized through use of sorting or dataflow-like processing networks. While there are other comparison algorithms, such as Miranker's TREAT, the best known comparison method having these attributes is the RETE algorithm ascribed to Forgey.
Forgey and Jackson discuss the RETE pattern/object matching method used in the AI production system control cycle. This method includes:
(a) compiling the condition elements of the pattern portion of a rule into an augmented data flowgraph (see Aho and Chambers) or a comparison sorting network (Forgey);
(b) comparing each object with conditions of the pattern as expressed in the compiled network over a set of nodes (alpha-nodes) that each test one object at a time;
(c) passing tokens indicative of a match from antecedent nodes to descendant nodes (beta-nodes) joined on a pattern-determined basis, comparing each token received at a descendant node, and passing tokens on to descendants in turn until the paths through the flowgraph are traversed; and
(d) maintaining a list of instantiations satisfying the match conditions expressed at each node.
In the remainder of this specification, the terms MAKE and CREATE, MODIFY and UPDATE, and REMOVE and DELETE will be used interchangeably. Also, the RECOGNIZE, RESOLVE, and ACT phases of the AI production system control cycle serve as synonyms for MATCH, SELECT, and EXECUTE.